package com.Questions.DP;

import java.util.*;

/**
 * 最大整除子集
 */
public class leetcode368 {
    /*
    如果 a 是整除子集S1 的最小整数 b的约数 那么可以将a加入到S1 中
    如果 c 是整除子集S2 的最大整数 d的倍数 那么可以将c加入到S2 中
     */
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int len=nums.length;
        Arrays.sort(nums);

        // 第一步 动态规划找出最大子集的个数 最大子集中的最大整数
        int[] dp=new int[len];
        Arrays.fill(dp,1);
        int maxSize=1;// 整除子集的 最大长度
        int maxVal=dp[0];//
        for(int i=1;i<len;i++){
            for(int j=0;j<i;j++){
                if(nums[i]%nums[j]==0){// 整除的可传递性 和 大于其实是相同的 同样具有最优子结构
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            if(dp[i]>maxSize){
                maxSize=dp[i];
                maxVal=nums[i];
            }
        }

        // 第二部 倒推获得最大子集
        List<Integer> res=new ArrayList<>();
        if(maxSize==1){
            res.add(nums[0]);
            return res;
        }
        for(int i=len-1;i>=0&&maxSize>0;i--){// 根据子集大小的变化 查找子集元素
            if(dp[i]==maxSize&&maxVal%nums[i]==0){
                res.add(nums[i]);
                maxVal=nums[i];
                maxSize--;
            }
        }
        return res;


    }
}
